#include <stdio.h>
#include <Windows.h>

#define USE_X86_EXTENDED_INTRINSICS

#ifdef _WINDLL
#  define SC_API extern "C" __declspec(dllexport)
#endif

/*
NanoDSA Copyright (c) 2013 Eric Lasota
Adapted from:
"python-ecdsa" Copyright (c) 2010 Brian Warner

Portions written in 2005 by Peter Pearson and placed in the public domain.

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/

#define DIGIT_TYPE unsigned int
#define DOUBLE_DIGIT_TYPE unsigned long long int

#ifdef USE_X86_EXTENDED_INTRINSICS
	#include <intrin.h>
	#pragma intrinsic(__emulu)
#endif


#define DIGITS(bits) (((bits) + (sizeof(_Tdigit) * 8 - 1)) / (sizeof(_Tdigit) * 8))
#define DIGITBITS (sizeof(_Tdigit) * 8)

template<class _Tdigit, class _Tdoubledigit>
struct Digit
{
	_Tdigit v;

	inline Digit() { }

	inline Digit(const _Tdigit i)
	{
		v = i;
	}

	inline Digit CAdd(const Digit &rs, bool &carry) const
	{
		Digit rv;
		_Tdigit compressedMax = ~static_cast<_Tdigit>(0);
		_Tdigit added = this->v + rs.v;
		carry = (added < this->v);
		rv.v = added;
		return rv;
	}

	inline void XMul(const Digit &rs, Digit &low, Digit &high) const
	{
#ifdef USE_X86_EXTENDED_INTRINSICS
		unsigned __int64 result = __emulu(v, rs.v);
		low.v = static_cast<_Tdigit>(result);
		high.v = static_cast<_Tdigit>(result >> (sizeof(Digit) * 8));
#else
		_Tdoubledigit expanded = static_cast<_Tdoubledigit>(this->v) * static_cast<_Tdoubledigit>(rs.v);
		low.v = static_cast<_Tdigit>(expanded);
		high.v = static_cast<_Tdigit>(expanded >> (sizeof(_Tdigit) * 8));
#endif
	}

	inline static Digit XDiv(const Digit &qhigh, const Digit &qlow, const Digit &divisor)
	{
#ifdef USE_X86_EXTENDED_INTRINSICS
		_Tdigit dhigh = qhigh.v;
		_Tdigit dlow = qlow.v;
		_Tdigit divisori = divisor.v;
		_Tdigit result;
		__asm
		{
			mov edx, dhigh
			mov eax, dlow
			div divisori
			mov result, eax
		}
		return result;
#else
		Digit result;
		_Tdoubledigit expanded = qhigh.v;
		expanded <<= (sizeof(_Tdigit) * 8);
		expanded |= qlow.v;
		result.v = static_cast<_Tdigit>(expanded / divisor.v);
		return result;
#endif
	}

	inline Digit operator <<(int s) const
	{
		Digit rv;
		rv.v = this->v << s;
		return rv;
	}

	inline Digit operator >>(int s) const
	{
		Digit rv;
		rv.v = this->v >> s;
		return rv;
	}

	inline Digit operator | (const Digit &rs) const
	{
		Digit rv;
		rv.v = this->v | rs.v;
		return rv;
	}

	inline Digit operator ~() const
	{
		Digit rv;
		rv.v = ~this->v;
		return rv;
	}

	inline Digit operator &(const Digit &rs) const
	{
		Digit rv;
		rv.v = this->v & rs.v;
		return rv;
	}

	inline Digit operator +(const Digit &rs) const
	{
		Digit rv;
		rv.v = this->v + rs.v;
		return rv;
	}

	inline Digit operator -(const Digit &rs) const
	{
		Digit rv;
		rv.v = this->v - rs.v;
		return rv;
	}

	inline bool operator >(const Digit &rs) const
	{
		return this->v > rs.v;
	}

	inline bool operator <(const Digit &rs) const
	{
		return this->v < rs.v;
	}

	inline bool operator !=(const Digit &rs) const
	{
		return this->v != rs.v;
	}

	inline bool operator ==(const Digit &rs) const
	{
		return this->v == rs.v;
	}

	inline unsigned char ToByte() const
	{
		return static_cast<unsigned char>(this->v);
	}
};

template<class _Tdigit, unsigned int _Tbits> struct ECurve;

template<class _Tdigit, unsigned int _Tbits>
struct BigNum
{
	_Tdigit _digits[DIGITS(_Tbits)];
	bool _negative;

	BigNum()
	{
		unsigned int numDigits = DIGITS(_Tbits);
		for(unsigned int i=0;i<numDigits;i++)
			_digits[i] = 0;
		_negative = false;
	}

	inline bool IsNegative() const
	{
		return _negative;
	}

	inline bool CheckBit(unsigned int bit) const
	{
		if(bit >= _Tbits)
			return false;

		unsigned int digitBits = sizeof(_Tdigit) * 8;
		unsigned int digit = bit / digitBits;
		unsigned int boffs = bit % digitBits;

		return ((_digits[digit] & (1 << boffs)) != 0);
	}

	inline void SetBit(unsigned int bit)
	{
		if(bit >= _Tbits)
			return;

		unsigned int digitBits = sizeof(_Tdigit) * 8;
		unsigned int digit = bit / digitBits;
		unsigned int boffs = bit % digitBits;

		_digits[digit] = _digits[digit] | (1 << boffs);
	}

	inline void Increment(unsigned int doffs)
	{
		unsigned int nDigits = DIGITS(_Tbits);
		while(doffs < nDigits)
		{
			_Tdigit maxDigit = ~static_cast<_Tdigit>(0);
			_Tdigit digitV = _digits[doffs].v + 1;
			_digits[doffs] = digitV;
			if(digitV == 0)
				doffs++;
			else
				break;
		}
	}

	inline void Accumulate(unsigned int doffs, _Tdigit value)
	{
		unsigned int nDigits = DIGITS(_Tbits);
		_Tdigit added = _digits[doffs] + value;
		_digits[doffs] = added;
		if(added < value)
		{
			// Carried
			Increment(doffs + 1);
		}
	}

	inline bool IsZero() const
	{
		unsigned int nDigits = DIGITS(_Tbits);
		for(unsigned int i=0;i<nDigits;i++)
			if(_digits[i] != 0)
				return false;
		return true;
	}
	
	inline static BigNum<_Tdigit, _Tbits> FromSingleDigit(const _Tdigit &rs)
	{
		BigNum<_Tdigit, _Tbits> rv;
		rv._digits[0] = rs;
		return rv;
	}
	
	inline static BigNum<_Tdigit, _Tbits> FromBytes(const unsigned char *bytes, bool negative)
	{
		BigNum<_Tdigit, _Tbits> rv;
		_Tdigit currentDigit = 0;
		unsigned int digitOffset = 0;
		unsigned int nBits = _Tbits;
		unsigned int bitOffset = 0;
		while(nBits)
		{
			currentDigit = currentDigit | ((*bytes++) << bitOffset);
			bitOffset += 8;
			if(bitOffset == DIGITBITS)
			{
				rv._digits[digitOffset++] = currentDigit;
				currentDigit = 0;
				bitOffset = 0;
			}

			if(nBits >= 8)
				nBits -= 8;
			else
				nBits = 0;
		}
		rv._negative = negative;
		return rv;
	}

	inline void ToBytes(unsigned char *bytes) const
	{
		
		BigNum<_Tdigit, _Tbits> rv;
		unsigned int digitOffset = 0;
		unsigned int nBits = _Tbits;
		unsigned int bitOffset = 0;

		while(nBits)
		{
			*bytes++ = (_digits[digitOffset] >> bitOffset).ToByte();
			bitOffset += 8;
			if(bitOffset == DIGITBITS)
			{
				digitOffset++;
				bitOffset = 0;
			}

			if(nBits >= 8)
				nBits -= 8;
			else
				nBits = 0;
		}
	}

	inline static BigNum<_Tdigit, _Tbits> FromString(const char *chars)
	{
		BigNum<_Tdigit, _Tbits> rv;
		bool negate = false;
		rv._negative = false;

		if(chars[0] == '-')
		{
			negate = true;
			chars++;
		}

		if(chars[0] == '0' && chars[1] == 'x')
		{
			BigNum<_Tdigit, 5> mul = BigNum<_Tdigit, 5>::FromSingleDigit(16);

			chars+=2;
			// Hex
			while(*chars)
			{
				char c = *chars++;
				_Tdigit d;
				if(c >= '0' && c <= '9')
					d = static_cast<_Tdigit>(c - '0');
				else if(c >= 'A' && c <= 'F')
					d = static_cast<_Tdigit>(c - 'A' + 0xA);
				else if(c >= 'a' && c <= 'f')
					d = static_cast<_Tdigit>(c - 'a' + 0xA);
				else
					d = 0;

				rv = ((rv * mul) + BigNum<_Tdigit, 4>::FromSingleDigit(d)).Resize<_Tbits>();
			}
		}
		else
		{
			BigNum<_Tdigit, 4> mul = BigNum<_Tdigit, 4>::FromSingleDigit(10);

			// Decimal
			while(*chars)
				rv = ((rv * mul) + BigNum<_Tdigit, 4>::FromSingleDigit((*chars++) - '0')).Resize<_Tbits>();
		}
		if(negate)
			rv._negative = true;
		return rv;
	}

	template<unsigned int _Trsbits>
	inline bool ValueGreater(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		unsigned int rsDigits = DIGITS(_Trsbits);
		unsigned int lsDigits = DIGITS(_Tbits);
		unsigned int maxDigits = lsDigits;
		if(rsDigits > lsDigits)
			maxDigits = rsDigits;

		for(unsigned int i=0;i<maxDigits;i++)
		{
			unsigned int d = maxDigits - i - 1;
			_Tdigit lsd = 0;
			_Tdigit rsd = 0;
			if(d < lsDigits)
				lsd = _digits[d];
			if(d < rsDigits)
				rsd = rs._digits[d];
			if(lsd > rsd)
				return true;
			if(rsd > lsd)
				return false;
		}
		return false;
	}

	template<unsigned int _Tnewbits>
	BigNum<_Tdigit, _Tnewbits> Resize() const
	{
		BigNum<_Tdigit, _Tnewbits> rv;
		rv._negative = _negative;
		unsigned int rsDigits = DIGITS(_Tnewbits);
		unsigned int thisDigits = DIGITS(_Tbits);

		for(unsigned int d=0;d<rsDigits;d++)
		{
			if(d >= thisDigits)
				rv._digits[d] = 0;
			else
				rv._digits[d] = _digits[d];
		}
		return rv;
	}
	
	template<unsigned int _Trsbits>
	inline BigNum<_Tdigit, ((_Tbits > _Trsbits) ? (_Tbits + 1) : (_Trsbits + 1))> Add(const BigNum<_Tdigit, _Trsbits> &rs, bool negateRS, bool setNegative) const
	{
		BigNum<_Tdigit, ((_Tbits > _Trsbits) ? (_Tbits + 1) : (_Trsbits + 1))> rv;
		unsigned int lsDigits = DIGITS(_Tbits);
		unsigned int rsDigits = DIGITS(_Trsbits);
		unsigned int outDigits = DIGITS((_Tbits > _Trsbits) ? (_Tbits + 1) : (_Trsbits + 1));

		for(unsigned int i=0;i<outDigits;i++)
		{
			if(i < lsDigits)
				rv._digits[i] = _digits[i];
			else
				rv._digits[i] = 0;
		}

		for(unsigned int i=0;i<outDigits;i++)
		{
			if(i < rsDigits)
			{
				if(negateRS)
					rv.Accumulate(i, ~rs._digits[i]);
				else
					rv.Accumulate(i, rs._digits[i]);
			}
			else
			{
				if(negateRS)
					rv.Accumulate(i, static_cast<_Tdigit>(0) - 1);
			}
		}
		if(negateRS)
			rv.Increment(0);
		rv._negative = setNegative;
		if(rv.IsZero())
			rv._negative = false;
		return rv;
	}
	
	template<unsigned int _Trsbits>
	inline BigNum<_Tdigit, ((_Tbits > _Trsbits) ? (_Tbits + 1) : (_Trsbits + 1))> operator +(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		if(rs._negative == _negative)
			return Add(rs, false, _negative);

		if(ValueGreater(rs))
			return Add(rs, true, _negative);
		return rs.Add(*this, true, !_negative);
	}
	
	template<unsigned int _Trsbits>
	inline bool operator ==(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		if(rs._negative != this->_negative)
			return false;

		unsigned int lsDigits = DIGITS(_Tbits);
		unsigned int rsDigits = DIGITS(_Trsbits);
		for(unsigned int i=0;i<lsDigits && i<rsDigits;i++)
			if(_digits[i] != rs._digits[i])
				return false;
		for(unsigned int i=lsDigits;i<rsDigits;i++)
			if(rs._digits[i] != 0)
				return false;
		for(unsigned int i=rsDigits;i<lsDigits;i++)
			if(_digits[i] != 0)
				return false;
		return true;
	}
	
	template<unsigned int _Trsbits>
	inline bool operator !=(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		return !((*this) == rs);
	}
	
	inline BigNum<_Tdigit, _Tbits> operator -() const
	{
		BigNum<_Tdigit, _Tbits> result = *this;
		result._negative = !_negative;
		return result;
	}
	
	inline BigNum<_Tdigit, _Tbits> operator >>(unsigned int bits) const
	{
		BigNum<_Tdigit, _Tbits> result;
		unsigned int digitBits = sizeof(_Tdigit) * 8;
		unsigned int droppedDigits = bits / digitBits;
		unsigned int shiftBits = bits % digitBits;
		unsigned int nDigits = DIGITS(_Tbits);

		for(unsigned int i=0;i<nDigits;i++)
		{
			unsigned int topSlotOffset = nDigits - i - 1;
			if(topSlotOffset < droppedDigits)
				result._digits[i] = 0;
			else
			{
				_Tdigit digit = this->_digits[i + droppedDigits] >> shiftBits;
				if(shiftBits != 0 && topSlotOffset > droppedDigits)
					digit = digit | (this->_digits[i + droppedDigits + 1] << (digitBits - shiftBits));
				result._digits[i] = digit;
			}
		}
		result._negative = this->_negative;

		return result;
	}
	
	inline BigNum<_Tdigit, _Tbits> operator <<(unsigned int bits) const
	{
		BigNum<_Tdigit, _Tbits> result;
		unsigned int digitBits = sizeof(_Tdigit) * 8;
		unsigned int droppedDigits = bits / digitBits;
		unsigned int shiftBits = bits % digitBits;
		unsigned int nDigits = DIGITS(_Tbits);

		for(unsigned int i=0;i<nDigits;i++)
		{
			if(i < droppedDigits)
				result._digits[i] = 0;
			else
			{
				_Tdigit digit = this->_digits[i - droppedDigits] << shiftBits;
				if(shiftBits != 0 && i > droppedDigits)
					digit = digit | (this->_digits[i - droppedDigits - 1] >> (digitBits - shiftBits));
				result._digits[i] = digit;
			}
		}
		result._negative = this->_negative;

		return result;
	}

	
	template<unsigned int _Trsbits>
	inline void DivMod(const BigNum<_Tdigit, _Trsbits> &rs, BigNum<_Tdigit, _Tbits> &outQuotient, BigNum<_Tdigit, _Trsbits> &outRemainder) const
	{
		BigNum<_Tdigit, _Tbits> remainder = *this;
		BigNum<_Tdigit, _Tbits> quotient;

		remainder._negative = false;
		quotient._negative = false;

		if(this->IsZero())
		{
			outRemainder = this->Resize<_Trsbits>();
			outQuotient = *this;
			return;
		}
		if(rs.IsZero())
		{
			BigNum<_Tdigit, _Tbits> zero;
			BigNum<_Tdigit, _Trsbits> zeroR;
			outQuotient = zero;
			outRemainder = zeroR;
			return;
		}

		if(rs.ValueGreater(*this))
		{
			// Divisor is higher than dividend
			BigNum<_Tdigit, _Tbits> quotient;	// Zero
			BigNum<_Tdigit, _Trsbits> remainder = this->Resize<_Trsbits>();
			if(this->_negative != rs._negative)
			{
				quotient.Increment(0);
				quotient._negative = true;
			}
			// Remainder won't be zero because if it was, it would have been caught by if(this->IsZero())
			if(this->_negative != rs._negative)
				remainder = rs.Add(remainder, true, false).Resize<_Trsbits>();
			remainder._negative = rs._negative;

			outRemainder = remainder;	
			outQuotient = quotient;
			return;
		}

		if(rs == *this)
		{
			BigNum<_Tdigit, _Tbits> remainder;	// Zero
			BigNum<_Tdigit, _Tbits> quotient;
			quotient.SetBit(0);					// One
			outRemainder = remainder.Resize<_Trsbits>();
			outQuotient = quotient;
			return;
		}

		unsigned int rsDigits = DIGITS(_Trsbits);
		unsigned int lsDigits = DIGITS(_Tbits);

		unsigned int highRSDigit=0;
		for(unsigned int d=0;d<rsDigits;d++)
			if(rs._digits[d] != 0)
				highRSDigit = d;
		unsigned int highLSDigit=0;
		for(unsigned int d=0;d<lsDigits;d++)
			if(_digits[d] != 0)
				highLSDigit = d;
		BigNum<_Tdigit, _Trsbits + DIGITBITS> longDivRemainder;
		unsigned int ldrDigits = DIGITS(_Trsbits) + 1;

		_Tdigit primaryDivideDigit = rs._digits[highRSDigit];

		// Fill long div remainder with high digits from LS
		for(unsigned int ldrd=0;ldrd<=highRSDigit;ldrd++)
			longDivRemainder._digits[ldrd] = _digits[ldrd + highLSDigit - highRSDigit];
		unsigned int numSteps = highLSDigit - highRSDigit + 1;

		for(unsigned int step=0;step<numSteps;step++)
		{
			if(step != 0)
			{
				// Add in another digit
				for(unsigned int shiftDigit=1;shiftDigit<ldrDigits;shiftDigit++)
					longDivRemainder._digits[ldrDigits-shiftDigit] = longDivRemainder._digits[ldrDigits-shiftDigit-1];
				longDivRemainder._digits[0] = _digits[numSteps - step - 1];
			}

			// DivMod longDivRemainder by rs --> divisionDigit = quotient, longDivRemainder = remainder
			_Tdigit guess;
			{
				_Tdigit highDigit = longDivRemainder._digits[highRSDigit+1];
				// In rare circumstances, the top digit can be the primary divide digit, which will cause an overflow
				if(highDigit == primaryDivideDigit)
					guess = ~static_cast<_Tdigit>(0);
				else
					guess = _Tdigit::XDiv(highDigit, longDivRemainder._digits[highRSDigit], primaryDivideDigit);
			}

			// We need the lowest digit where (digit * rs) <= longDivRemainder
			// The initial guess will usually be either the correct answer or 1 + the correct answer and will never be over the correct answer
			// The number of search steps needed can also only be as great as the bit headroom of rs
			// The correct answer is always in the range (floor(initialGuess/2)..initialGuess)
			//
			// Benchmarks:
			// Initial guess correct: 74.2%
			// Subtract-one hits: 23.56%
			// Binary search required: 2.2%
			// Average steps required for binary search to hit: 4.3

			{
				BigNum<_Tdigit, _Trsbits + DIGITBITS> dmul;
				if(guess != 0)
					dmul = rs * BigNum<_Tdigit, DIGITBITS>::FromSingleDigit(guess);
				// See if we got an exact hit
				if(!dmul.ValueGreater(longDivRemainder))
				{
					longDivRemainder = (longDivRemainder - dmul).Resize<_Trsbits + DIGITBITS>();
					quotient._digits[numSteps - step - 1] = guess;
				}
				else
				{
					// Try subtracting 1
					BigNum<_Tdigit, _Trsbits + DIGITBITS + 1> dmul_minus_rs = (dmul - rs);
					if(!dmul_minus_rs.ValueGreater(longDivRemainder))
					{
						quotient._digits[numSteps - step - 1] = guess - 1;
						longDivRemainder = (longDivRemainder - dmul_minus_rs).Resize<_Trsbits + DIGITBITS>();
					}
					else
					{
						// Still didn't find it, binary search for it
						_Tdigit maxExclusive = guess - 1;
						_Tdigit minInclusive = guess >> 1;
						
						BigNum<_Tdigit, _Trsbits + DIGITBITS> lastGoodDMul;

						while(true)
						{
							_Tdigit newGuess = minInclusive + ((maxExclusive - minInclusive) >> 1);
							bool mustTerminate = (maxExclusive - minInclusive == 1);
							dmul = rs * BigNum<_Tdigit, DIGITBITS>::FromSingleDigit(newGuess);
							if(mustTerminate || !dmul.ValueGreater(longDivRemainder))
							{
								lastGoodDMul = dmul;
								minInclusive = newGuess;
								if(mustTerminate)
									break;
							}
							else
								maxExclusive = newGuess;
						}

						quotient._digits[numSteps - step - 1] = minInclusive;
						longDivRemainder = (longDivRemainder - lastGoodDMul).Resize<_Trsbits + DIGITBITS>();
					}
				}
			}
		}

		BigNum<_Tdigit, _Trsbits> reducedRemainder = longDivRemainder.Resize<_Trsbits>();
		/*
		unsigned int highRSBit = 0;
		for(unsigned int bit=0;bit<_Trsbits;bit++)
			if(rs.CheckBit(bit))
				highRSBit = bit;
		unsigned int highLSBit = 0;
		for(unsigned int bit=0;bit<_Tbits;bit++)
			if(this->CheckBit(bit))
				highLSBit = bit;


		unsigned int numCompares = (highLSBit - highRSBit) + 1;
		BigNum<_Tdigit, _Tbits> scrollingDivisor = rs.Resize<_Tbits>() << (numCompares - 1);
		scrollingDivisor._negative = false;
		for(unsigned int i=0;i<numCompares;i++)
		{
			if(remainder.ValueGreater(scrollingDivisor))
			{
				quotient.SetBit(numCompares - i - 1);
				remainder = (remainder - scrollingDivisor).Resize<_Tbits>();
			}
			else if(remainder == scrollingDivisor)
			{
				// Exhausted the entire remainder
				quotient.SetBit(numCompares - i - 1);

				if(rs._negative != this->_negative)
					quotient._negative = true;

				outQuotient = quotient;
				BigNum<_Tdigit, _Trsbits> zero;
				outRemainder = zero;
				return;
			}
			scrollingDivisor = scrollingDivisor >> 1;
		}
		BigNum<_Tdigit, _Trsbits> reducedRemainder = remainder.Resize<_Trsbits>();
		*/

		if(this->_negative != rs._negative && !reducedRemainder.IsZero())
			reducedRemainder = rs.Add(reducedRemainder, true, false).Resize<_Trsbits>();
		reducedRemainder._negative = rs._negative;

		if(rs._negative != this->_negative)
		{
			quotient.Increment(0);
			quotient._negative = true;
		}

		outRemainder = reducedRemainder;
		outQuotient = quotient;
	}

	template<unsigned int _Trsbits>
	inline BigNum<_Tdigit, _Trsbits> operator %(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		BigNum<_Tdigit, _Tbits> quotient;
		BigNum<_Tdigit, _Trsbits> remainder;
		DivMod<_Trsbits>(rs, quotient, remainder);
		return remainder;
	}

	template<unsigned int _Trsbits>
	inline BigNum<_Tdigit, ((_Tbits > _Trsbits) ? (_Tbits + 1) : (_Trsbits + 1))> operator -(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		if(rs._negative != _negative)
			return Add(rs, false, _negative);

		if(ValueGreater(rs))
			return Add(rs, true, _negative);
		return rs.Add(*this, true, !_negative);
	}

	template<unsigned int _Trsbits>
	inline BigNum<_Tdigit, _Tbits + _Trsbits> operator *(const BigNum<_Tdigit, _Trsbits> &rs) const
	{
		BigNum<_Tdigit, _Tbits + _Trsbits> rv;
		unsigned int lsDigits = DIGITS(_Tbits);
		unsigned int rsDigits = DIGITS(_Trsbits);
		unsigned int outDigits = DIGITS(_Tbits + _Trsbits);

		for(unsigned int i=0;i<outDigits;i++)
			rv._digits[i] = 0;

		for(unsigned int lsd=0;lsd<lsDigits;lsd++)
		{
			_Tdigit lsDigit = _digits[lsd];
			unsigned int placeD = lsd;
			for(unsigned int rsd=0;rsd<rsDigits;rsd++)
			{
				if(placeD == outDigits)
					break;
				_Tdigit dmlow, dmhigh;
				lsDigit.XMul(rs._digits[rsd], dmlow, dmhigh);
				rv.Accumulate(placeD, dmlow);
				placeD++;
				if(placeD == outDigits)
					break;
				rv.Accumulate(placeD, dmhigh);
			}
		}
		rv._negative = (rs._negative != this->_negative);
		return rv;
	}

	template<unsigned int _Trsbits>
	inline BigNum<_Tdigit, _Tbits> InverseMod(const BigNum<_Tdigit, _Trsbits> &m, bool &valid) const
	{
		// Inverse of a mod m.
		BigNum<_Tdigit, _Tbits> a = *this;
		if(this->IsNegative() || m == a || !m.ValueGreater(a))
			a = (a % m).Resize<_Tbits>();

		// From Ferguson and Schneier, roughly:
		BigNum<_Tdigit, _Tbits> c = a;
		BigNum<_Tdigit, _Tbits> d = m.Resize<_Tbits>();
		BigNum<_Tdigit, _Tbits * 2> uc;		uc.SetBit(0);	// = 1
		BigNum<_Tdigit, _Tbits * 2> vc;
		BigNum<_Tdigit, _Tbits * 2> ud;
		BigNum<_Tdigit, _Tbits * 2> vd;		vd.SetBit(1);	// = 1

		int iteration = 0;

		while(!c.IsZero())
		{
			BigNum<_Tdigit, _Tbits> oldC = c;
			BigNum<_Tdigit, _Tbits> q;
			BigNum<_Tdigit, _Trsbits> r;
			d.DivMod(c, q, c);
			d = oldC;

			BigNum<_Tdigit, _Tbits * 2> oldVC = vc;
			BigNum<_Tdigit, _Tbits * 2> oldUC = uc;
			uc = (ud - q*uc).Resize<_Tbits * 2>();
			vc = (vd - q*vc).Resize<_Tbits * 2>();
			ud = oldUC;
			vd = oldVC;

			iteration++;
		}
		// At this point, d is the GCD, and ud*a+vd*m = d.
		// If d == 1, this means that ud is a inverse.
		if(d != BigNum<_Tdigit, 1>::FromSingleDigit(1))
		{
			BigNum<_Tdigit, _Tbits> result;
			valid = false;
			return result;
		}
		if(ud.IsZero() || ud.IsNegative())
			return (ud + m).Resize<_Tbits>();
		return ud.Resize<_Tbits>();
	}
};


template<class _Tdigit, unsigned int _Tbits>
struct EPoint
{
private:
	const ECurve<_Tdigit, _Tbits> *_curve;
	BigNum<_Tdigit, _Tbits> _x;
	BigNum<_Tdigit, _Tbits> _y;
	BigNum<_Tdigit, _Tbits> _order;
	bool _orderSet;
	bool _isInfinite;

public:
	inline EPoint()
	{
		_curve = NULL;
		_isInfinite = false;
		_orderSet = false;
	}

	inline static EPoint<_Tdigit, _Tbits> Infinity()
	{
		EPoint<_Tdigit, _Tbits> result;
		result._isInfinite = true;
		return result;
	}

	inline BigNum<_Tdigit, _Tbits> X() const
	{
		return _x;
	}

	inline BigNum<_Tdigit, _Tbits> Y() const
	{
		return _y;
	}

	inline BigNum<_Tdigit, _Tbits> Order() const
	{
		return _order;
	}

	inline bool IsInfinite() const
	{
		return _isInfinite;
	}

	inline EPoint<_Tdigit, _Tbits> Mul(const BigNum<_Tdigit, _Tbits> &rs, bool &valid) const
	{
		EPoint<_Tdigit, _Tbits> result;
		BigNum<_Tdigit, _Tbits> e = rs;

		if(this->_orderSet)
			e = e % _order;
		if(e.IsZero())
			return EPoint<_Tdigit, _Tbits>::Infinity();
		if(IsInfinite())
			return *this;
		if(e.IsZero() || e.IsNegative())
		{
			valid = false;
			return result;
		}
		// From X9.62 D.3.2:
		BigNum<_Tdigit, _Tbits + 2> e3 = e * BigNum<_Tdigit, 2>::FromSingleDigit(3);
		EPoint<_Tdigit, _Tbits> negativeSelf = EPoint::From(_curve, _x, -_y, _orderSet ? &_order : NULL, valid);
		if(!valid)
			return result;

		unsigned int highBit = 0;
		for(unsigned int bit=0;bit<_Tbits+2;bit++)
			if(e3.CheckBit(bit))
				highBit = bit;

		result = *this;

		for(unsigned int bit=0;bit<highBit-1;bit++)
		{
			unsigned int dbit = highBit - bit - 1;
			bool echeck = e.CheckBit(dbit);
			bool e3check = e3.CheckBit(dbit);
			result = result.Double(valid);
			if(!valid)
			{
				return result;
			}
			if(e3check && !echeck)
			{
				result = result.Add(*this, valid);
				if(!valid)
					return result;
			}
			else if(echeck && !e3check)
			{
				result = result.Add(negativeSelf, valid);
				if(!valid)
					return result;
			}
		}

		return result;
	}

	inline EPoint<_Tdigit, _Tbits> Double(bool &valid) const
	{
		// Return a new point that is twice the old.
		if(this->IsInfinite())
			return Infinity();
		// X9.62 B.3:
		const BigNum<_Tdigit, _Tbits> &p = _curve->_p;
		const BigNum<_Tdigit, _Tbits> &a = _curve->_a;

		BigNum<_Tdigit, 2> three = BigNum<_Tdigit, 2>::FromSingleDigit(3);
		BigNum<_Tdigit, 3 + _Tbits + _Tbits> l1 = BigNum<_Tdigit, 2>::FromSingleDigit(3) * this->_x * this->_x + a;
		BigNum<_Tdigit, _Tbits + 1> imod = (_y.Resize<_Tbits + 1>() << 1).InverseMod(p.Resize<_Tbits + 1>(), valid);
		if(!valid)
		{
			EPoint<_Tdigit, _Tbits> result;
			return result;
		}
		BigNum<_Tdigit, _Tbits> l = (l1 * imod) % p;
		BigNum<_Tdigit, _Tbits> x3 = (l * l - (_x + _x)) % p;
		BigNum<_Tdigit, _Tbits> y3 = (l * (_x - x3) - _y) % p;

		BigNum<_Tdigit, _Tbits + 1> check1 = _x - x3;
		BigNum<_Tdigit, (_Tbits+_Tbits+1)> check2 = l * check1;
		BigNum<_Tdigit, (_Tbits+_Tbits+2)> check3 = check2 - _y;
		BigNum<_Tdigit, _Tbits> check4 = check3 % p;

		return EPoint<_Tdigit, _Tbits>::From(_curve, x3, y3, NULL, valid);
	}

	inline static EPoint<_Tdigit, _Tbits> From(const ECurve<_Tdigit, _Tbits> *curve, BigNum<_Tdigit, _Tbits> x, BigNum<_Tdigit, _Tbits> y, const BigNum<_Tdigit, _Tbits> *order, bool &valid)
	{
		EPoint<_Tdigit, _Tbits> pt;
		pt._x = x;
		pt._y = y;
		pt._curve = curve;
		pt._isInfinite = false;

		if(!curve->ContainsPoint(x, y))
		{
			valid = false;
			return pt;
		}
		if(order != NULL)
		{
			pt._order = *order;
			pt._orderSet = true;
			if(!(pt.Mul(*order, valid).IsInfinite()))
			{
				valid = false;
				return pt;
			}
			if(!valid)
				return pt;
		}
		return pt;
	}

	inline EPoint<_Tdigit, _Tbits> Add(const EPoint<_Tdigit, _Tbits> &other, bool &valid)
	{
		// Add one point to another point.

		// X9.62 B.3:
		if(other.IsInfinite())
			return *this;
		if(this->IsInfinite())
			return other;

		if(this->_x == other._x)
		{
			if(((this->_y + other._y) % this->_curve->_p).IsZero())
				return EPoint<_Tdigit, _Tbits>::Infinity();
			else
				return this->Double(valid);
		}

		BigNum<_Tdigit, _Tbits> p = this->_curve->_p;
		BigNum<_Tdigit, _Tbits + 1> imod = (other._x - this->_x).InverseMod(p, valid);
		if(!valid)
		{
			EPoint<_Tdigit, _Tbits> result;
			return result;
		}
		BigNum<_Tdigit, _Tbits> l = ( ( other._y - this->_y ) * imod ) % p;

		BigNum<_Tdigit, _Tbits> x3 = ( l * l - this->_x - other._x ) % p;
		BigNum<_Tdigit, _Tbits> y3 = ( l * ( this->_x - x3 ) - this->_y ) % p;
		return EPoint<_Tdigit, _Tbits>::From(_curve, x3, y3, NULL, valid);
	}
};

template<class _Tdigit, unsigned int _Tbits>
struct ECurve
{
	BigNum<_Tdigit, _Tbits> _p;
	BigNum<_Tdigit, _Tbits> _a;
	BigNum<_Tdigit, _Tbits> _b;

	EPoint<_Tdigit, _Tbits> _generator;

	inline ECurve(const char *pstr, const char *rstr, const char *astr,
		const char *bstr, const char *Gxstr, const char *Gystr)
	{
		bool valid;
		_p = BigNum<_Tdigit, _Tbits>::FromString(pstr);
		_a = BigNum<_Tdigit, _Tbits>::FromString(astr);
		_b = BigNum<_Tdigit, _Tbits>::FromString(bstr);
		BigNum<_Tdigit, _Tbits> order = BigNum<_Tdigit, _Tbits>::FromString(rstr);

		_generator = EPoint<_Tdigit, _Tbits>::From(this, BigNum<_Tdigit, _Tbits>::FromString(Gxstr),
			BigNum<_Tdigit, _Tbits>::FromString(Gystr),
			&order, valid);
	}

	inline bool ContainsPoint(const BigNum<_Tdigit, _Tbits> &x, const BigNum<_Tdigit, _Tbits> &y) const
	{
		//Is the point (x,y) on this curve?
		return (( y * y - ( x * x * x + this->_a * x + this->_b ) ) % this->_p).IsZero();
	}
};

typedef Digit<unsigned int, unsigned long long int> FastDigit;

ECurve<FastDigit, 192> NIST192p("6277101735386680763835789423207666416083908700390324961279",
	"6277101735386680763835789423176059013767194773182842284081",
	"-3",
	"0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
	"0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
	"0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811");

ECurve<FastDigit, 224> NIST224p("26959946667150639794667015087019630673557916260026308143510066298881",
	"26959946667150639794667015087019625940457807714424391721682722368061",
	"-3",
	"0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
	"0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
	"0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34");

ECurve<FastDigit, 256> NIST256p("115792089210356248762697446949407573530086143415290314195533631308867097853951",
	"115792089210356248762697446949407573529996955224135760342422259061068512044369",
	"-3",
	"0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
	"0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
	"0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5");


ECurve<FastDigit, 384> NIST384p("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319",
	"39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643",
	"-3",
	"0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef",
	"0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7",
	"0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f");

ECurve<FastDigit, 521> NIST521p("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151",
	"6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449",
	"-3",
	"0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
	"0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
	"0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650");


ECurve<FastDigit, 256> SECP256k1("0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
	"0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
	"0x0000000000000000000000000000000000000000000000000000000000000000",
	"0x0000000000000000000000000000000000000000000000000000000000000007",
	"0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
	"0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8");


template<class _Tdigit, unsigned int _Tbits>
void SmallCrypt_DSA_Sign(const ECurve<_Tdigit, _Tbits> &curve, const BigNum<_Tdigit, _Tbits> &k, const BigNum<_Tdigit, _Tbits> &digest, const BigNum<_Tdigit, _Tbits> &privkey,
	BigNum<_Tdigit, _Tbits> &outR, BigNum<_Tdigit, _Tbits> &outS, bool &badK, bool &valid)
{
	if(k.IsZero())
	{
		badK = true;
		return;
	}
	const EPoint<_Tdigit, _Tbits> &G = curve._generator;
	const BigNum<_Tdigit, _Tbits> n = G.Order();
	EPoint<_Tdigit, _Tbits> p1 = G.Mul(k, valid);
	if(!valid)
		return;
	BigNum<_Tdigit, _Tbits> r = p1.X();
	if(r.IsZero())
	{
		badK = true;
		return;
	}

	BigNum<_Tdigit, _Tbits> imod = k.InverseMod(n, valid);
	if(!valid)
		return;
	BigNum<_Tdigit, _Tbits> s = ( imod * ( digest + ( privkey * r ) % n ) ) % n;
	if(s.IsZero())
	{
		badK = true;
		return;
	}
	outS = s;
	outR = r;
}

template<class _Tdigit, unsigned int _Tbits>
bool SmallCrypt_DSA_Verify(const ECurve<_Tdigit, _Tbits> &curve, const BigNum<_Tdigit, _Tbits> &sigR, const BigNum<_Tdigit, _Tbits> &sigS, const BigNum<_Tdigit, _Tbits> &digest, const EPoint<_Tdigit, _Tbits> &pubkey)
{
	bool valid = true;
	// From X9.62 J.3.1.

	//G = self.generator
	const BigNum<_Tdigit, _Tbits> n = curve._generator.Order();
	if(sigR.IsNegative() || sigR == n || sigR.ValueGreater(n))
		return false;
	if(sigS.IsNegative() || sigS == n || sigS.ValueGreater(n))
		return false;
	BigNum<_Tdigit, _Tbits> c = sigS.InverseMod(n, valid);
	if(!valid)
		return false;
	BigNum<_Tdigit, _Tbits> u1 = (digest * c) % n;
	BigNum<_Tdigit, _Tbits> u2 = (sigR * c) % n;
	EPoint<_Tdigit, _Tbits> xy1 = curve._generator.Mul(u1, valid);
	if(!valid)
		return false;
	EPoint<_Tdigit, _Tbits> xy2 = pubkey.Mul(u2, valid);
	if(!valid)
		return false;
	EPoint<_Tdigit, _Tbits> xy = xy1.Add(xy2, valid);
	if(!valid)
		return false;
	BigNum<_Tdigit, _Tbits> v = xy.X() % n;

	return v == sigR;
}

bool SmallCrypt_Random(void *buf, size_t len);

template<class _Tdigit, unsigned int _Tbits>
class ECUtils
{
public:
	inline static bool GeneratePrivateKey(const ECurve<_Tdigit, _Tbits> &curve, unsigned char *outPrivateKey)
	{
		unsigned char randBuf[(_Tbits + 7) / 8];
		BigNum<_Tdigit, _Tbits> secexp;
		BigNum<_Tdigit, _Tbits> order = curve._generator.Order();

		do
		{
			if(!SmallCrypt_Random(randBuf, (_Tbits + 7) / 8))
				return false;
			secexp = BigNum<_Tdigit, _Tbits>::FromBytes(randBuf, false);
		} while(secexp.IsZero() || secexp == order || secexp.ValueGreater(order));

		secexp.ToBytes(outPrivateKey);
		return true;
	}

	inline static bool GeneratePublicKey(const ECurve<_Tdigit, _Tbits> &curve, const unsigned char *privateKey, unsigned char *outPublicKey)
	{
		BigNum<_Tdigit, _Tbits> secexp = BigNum<_Tdigit, _Tbits>::FromBytes(privateKey, false);
		BigNum<_Tdigit, _Tbits> order = curve._generator.Order();

		bool valid = true;
		EPoint<_Tdigit, _Tbits> pubKeyPoint = curve._generator.Mul(secexp, valid);
		if(!valid)
			return false;
		pubKeyPoint.X().ToBytes(outPublicKey);
		pubKeyPoint.Y().ToBytes(outPublicKey + (_Tbits + 7) / 8);
		return true;
	}

	inline static bool Sign(const ECurve<_Tdigit, _Tbits> &curve, const unsigned char *digestBytes, const unsigned char *privateKey, unsigned char *outSignature)
	{
		BigNum<_Tdigit, _Tbits> secexp = BigNum<_Tdigit, _Tbits>::FromBytes(privateKey, false);
		BigNum<_Tdigit, _Tbits> digest = BigNum<_Tdigit, _Tbits>::FromBytes(digestBytes, false);
		unsigned char randBuf[(_Tbits + 7) / 8];
		BigNum<_Tdigit, _Tbits> sigR, sigS;
		bool badK = true;
		while(badK)
		{
			bool valid = true;
			badK = false;
			if(!SmallCrypt_Random(randBuf, (_Tbits + 7) / 8))
				return false;
			BigNum<_Tdigit, _Tbits> randomK = BigNum<_Tdigit, _Tbits>::FromBytes(randBuf, false);
			SmallCrypt_DSA_Sign<_Tdigit, _Tbits>(curve, randomK, digest, secexp, sigR, sigS, badK, valid);
			if(!valid)
				return false;
		}
		sigR.ToBytes(outSignature);
		sigS.ToBytes(outSignature + (_Tbits + 7) / 8);
		return true;
	}

	inline static bool Verify(const ECurve<_Tdigit, _Tbits> &curve, const unsigned char *digestBytes, const unsigned char *publicKey, const unsigned char *signature)
	{
		BigNum<_Tdigit, _Tbits> sigR = BigNum<_Tdigit, _Tbits>::FromBytes(signature, false);
		BigNum<_Tdigit, _Tbits> sigS = BigNum<_Tdigit, _Tbits>::FromBytes(signature + (_Tbits + 7) / 8, false);
		BigNum<_Tdigit, _Tbits> digest = BigNum<_Tdigit, _Tbits>::FromBytes(digestBytes, false);
		BigNum<_Tdigit, _Tbits> pubKeyX = BigNum<_Tdigit, _Tbits>::FromBytes(publicKey, false);
		BigNum<_Tdigit, _Tbits> pubKeyY = BigNum<_Tdigit, _Tbits>::FromBytes(publicKey + (_Tbits + 7) / 8, false);

		bool valid = true;
		EPoint<_Tdigit, _Tbits> pubKeyPoint = EPoint<_Tdigit, _Tbits>::From(&curve, pubKeyX, pubKeyY, NULL, valid);
		if(!valid)
			return false;

		return SmallCrypt_DSA_Verify<_Tdigit, _Tbits>(curve, sigR, sigS, digest, pubKeyPoint);
	}

};

#define EXPORT_FUNCS(curveName, bits)\
SC_API int SmallCrypt_##curveName##_GeneratePrivateKey(unsigned char *privateKey)\
{\
	return ECUtils<FastDigit, bits>::GeneratePrivateKey(curveName, privateKey);\
}\
\
SC_API int SmallCrypt_##curveName##_GeneratePublicKey(const unsigned char *privateKey, unsigned char *publicKey)\
{\
	return ECUtils<FastDigit, bits>::GeneratePublicKey(curveName, privateKey, publicKey);\
}\
\
SC_API int SmallCrypt_##curveName##_Sign(const unsigned char *digest, const unsigned char *privateKey, unsigned char *signature)\
{\
	return ECUtils<FastDigit, bits>::Sign(curveName, digest, privateKey, signature);\
}\
\
SC_API int SmallCrypt_##curveName##_Verify(const unsigned char *digest, const unsigned char *publicKey, unsigned char *signature)\
{\
	return ECUtils<FastDigit, bits>::Verify(curveName, digest, publicKey, signature);\
}

EXPORT_FUNCS(NIST192p, 192)
EXPORT_FUNCS(NIST224p, 224)
EXPORT_FUNCS(NIST256p, 256)
EXPORT_FUNCS(NIST384p, 384)
EXPORT_FUNCS(NIST521p, 521)
